package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/18 13:34
 *
 对称二叉树：从两个方向遍历整棵树，然后比对
 按之字形打印二叉树：树的层序遍历,在这基础上判断层数进行不同处理即可


序列化二叉树：
前序序列化，前序反序列化，因为常用前序创建
注意:因为数字长度可能为多位，可以在序列化是记录长度
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main40 {
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }

    StringBuilder sb=new StringBuilder();
    int index=0;
    String Serialize(TreeNode root) {
        if(root==null){
            sb.append('#');
            return sb.toString();
        }
        int v=root.val;
        int bit=v==0?1:0;
        while(v!=0){
            bit++;
            v/=10;
        }
        //序列化为：2 13，就是先读长度，再读数字
        sb.append(bit);
        sb.append(root.val);
        Serialize(root.left);
        Serialize(root.right);
        return sb.toString();
    }

    TreeNode Deserialize(String str) {
        if(index==str.length())return null;
        char ch=str.charAt(index);
        if(ch=='#'){
            index++;
            return null;
        }
        int len=ch-'0';
        int v=0;
        index++;
        while(len-->0){
            int t=str.charAt(index++)-'0';
            v=v*10+t;
        }
        TreeNode root=new TreeNode(v);

        root.left=Deserialize(str);
        root.right=Deserialize(str);
        return root;
    }


    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>>ans=new ArrayList<>();
        if(pRoot==null)return ans;
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(pRoot);
        int level=1;
        while(!queue.isEmpty()){
            int len=queue.size();
            ArrayList<Integer>tmp=new ArrayList<>();
            //层序遍历
            for(int i=0;i<len;++i){
                TreeNode t=queue.poll();
                if(t.left!=null){
                    queue.offer(t.left);
                }
                if(t.right!=null){
                    queue.offer(t.right);
                }
                //奇数顺序,偶数逆序
                if(level%2!=0){
                    tmp.add(t.val);
                }else{
                    tmp.add(0,t.val);
                }
            }
            level++;
            ans.add(tmp);
        }
        return ans;
    }

    boolean dfs(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null)return true;
        if(root1==null||root2==null)return false;
        if(root1.val!=root2.val)return false;
        return dfs(root1.left,root2.right)&&dfs(root1.right,root2.left);
    }

    boolean isSymmetrical(TreeNode pRoot) {
        return dfs(pRoot,pRoot);
    }
}
